/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package compare;

import java.util.ArrayList;

/**
 *
 * @author user1
 */
public class CompareUnited {
    public static final int NOT_FOUND = -1;
    public static int ms;
    
    public static int compareBruteForce(String pattern, String teks) {
        int pass = 0, check = 0, found = NOT_FOUND;
        while ((found == NOT_FOUND) && (pass <= (teks.length() - pattern.length()))) {
            check = 0;
            while ((check < pattern.length()) && (teks.charAt(pass + check) == pattern.charAt(check)))
                ++check;
            if (check == pattern.length())
                found = pass;
            else ++pass;
        }
        return found;
    }
    
    /**
     * @param args the command line arguments
     */
    public static ArrayList<Integer> HitungPinggiran(String P) {
        ArrayList<Integer> value  = new ArrayList<Integer>();
        int k,q;
        
        value.add(0);

        k = 0;
        
        for (q = 1;q<P.length();q++) {
            while ((k > 0) && (P.charAt(q) != P.charAt(k))) {
                k = value.get(k-1);
            }
            if (P.charAt(q) == P.charAt(k)) {
                k++;
            }
        
            value.add(k);
        }
        return value; 
    }
    
    public static int compareKMP (String P, String T) {
        int idx;
        int i=0,j=0;
        Boolean ok = false;
        ArrayList<Integer> b = new ArrayList<Integer>();
        
        b = HitungPinggiran(P);
        
        while ((i < T.length()) && !ok) {            
            while ((j>0) && (P.charAt(j) != T.charAt(i))) {                
                j = b.get(j-1);
            }
            
            if (P.charAt(j) == T.charAt(i)) {
                           j++;
            }
            
            if (j == P.length()) {
                ok = true;
            } else {
                i++;
            }
            
        }
        
        if (ok) {
            idx = i - P.length() + 1;
        } else {
            idx = -1;
        }
        
        return idx;
        
        
    }
    
    public static int compareBoyerMoore (String s, String m) {
        int ext = NOT_FOUND;
        ms = m.length();
        int n = s.length();
        int i,j,shift,bmBcShift,bmGsShift;
        int[] BmBc = new int[256];
        int[] BmGs = new int[n];
        
        BmBc = preBmBc(s,n,BmBc);
        BmGs = preBmGs(s,n,BmGs);
        i = 0;
        while (i <= (ms-n)) {
            j = n-1;
            while (j >= 0 && (m.charAt(i+j)%256 == s.charAt(j)%256)) {
                j--;
            }
            if (j < 0) {
                return i;
            }
            bmBcShift = BmBc[m.charAt(i+j)%256]-n+j+1;
            bmGsShift = BmGs[j];
            shift = Math.max(bmBcShift, bmGsShift);
            i+=shift;
        }
        return ext;
    }
    
    private static int[] preBmBc (String s, int n, int[] bmbc) {
        int[] bmBc = bmbc;
        for (int i = 0; i < 256; i++) {
            bmBc[i] = n;
        }
        for (int i = 0; i < n -1; i++) {
            bmBc[s.charAt(i)%256] = n - i - 1;
        }
        return bmBc;
    }
    
    private static int[] preSuffix (String s, int n, int[] suff) {
        int[] suf = suff;
        int f,g,i;
        f = n-1;
        suf[n-1] = n;
        g = n -1;
        for (i = n -2; i >= 0; i--) {
            if (i > g) {
                if (suff[i+n-1-f] < i - g) {
                    suf[i] = suf[i+n-1-f];
                }
            } else {
                if (i < g) {
                    g = i;
                }
                f = i;
                while (g >= 0 && s.charAt(g) == s.charAt(g+n-1-f)) {
                    --g;
                }
                suf[i] = f - g;
            }
        }
        return suf;
    }
    
    private static int[] preBmGs (String s, int n, int[] bmgs) {
        int[] bmGs = bmgs;
        int i,j;
        int[] suff = new int[n];
        
        suff = preSuffix(s, n, suff);
        
        for (i = 0; i < n; i++) {
            bmGs[i] = n;
        }
        j = 0;
        for (i = n-1; i >=0; i--) {
            if (suff[i] == i+1) {
                for (j = j; j <= n -2 -i; j++) {
                    if (bmGs[j] == n) {
                        bmGs[j] = n-1-i;
                    }
                }
            }
        }
        for (i = 0; i < n -1; i++) {
            bmGs[n-1-suff[i]] = n-1-i;
        }
        return bmGs;
    }
    
    
}
